#include "BinaryTree.h"
// #include "LinkQueue.h"
#include <iostream>

BinaryTree::BinaryTree()
{
    root = nullptr;
}

void BinaryTree::show()
{
    std::cout<<"前:";
    PrevTravel(root); //把根传到下面那个函数，从根开始找
    std::cout<<std::endl;

    std::cout<<"中:";
    MidTravel(root);
    std::cout<<std::endl;

    std::cout<<"后:";
    PostTravel(root);
    std::cout<<std::endl;

    std::cout<<"层序:";
    OrderTravel(root);
    std::cout<<std::endl;
}

// void BinaryTree::IsComplete()
// {
//     IsComplete(root);
// }

void BinaryTree::Insert(const ElementType &element)
{
    root = InsertNode(root,element); //把根返回，否则根一直为空
}

//返回值要把域(BinaryTree::)写出来，因为它是面向域的
BinaryTree::TreeNode *BinaryTree::InsertNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr) //根节点
    {
        return new TreeNode(element);//给空节点赋值，然后返回上面的插入函数
    }
    
    if(node->value == element)//要插入的数据树里已经有了
    {
        return node;
    }

    if(node->value > element) //node比要插入的数据大
    {
        
        node->left = InsertNode(node->left,element);//递归插入左子树
        if(LeftRightDev(node) > 1) //左边重
        {
            if(element < node->left->value) //左左失衡，右旋
            {
                node = RotateRight(node);
            }
            else //左右失衡，左右旋
            {
                node = RotateLeftRight(node);
            }
        }
    }

    else //根比要插入的数据小
    {
        //递归插入右子树
        node->right = InsertNode(node->right,element);

        if(LeftRightDev(node) < -1) //右边重
        {
            if(element > node->right->value) //右右失衡，左旋
            {
                node = RotateLeft(node);
            }
            else //右左失衡，右左旋
            {
                node = RotateRightLeft(node);
            }
        }
    }
    return node;

    // if(node == nullptr)
    // {
    //     return new TreeNode(element);
    // }
    // if(node->value == element)
    // {
    //     return node;
    // }
    // if(node->value > element)
    // {
    //     node->left = InsertNode(node->left,element);
    // }
    // else
    // {
    //     node->right = InsertNode(node->right,element);
    // }
    // return node;
    
}

void BinaryTree::PrevTravel(TreeNode *node)
{
    // if(node == nullptr)
    // {
    //     return;
    // }
    // std::cout<<node->value<<" ";
    // PrevTravel(node->left);
    // PrevTravel(node->right);
    if(node == nullptr)
    {
        return;
    }
    std::cout<<*(int *)node->value<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void BinaryTree::MidTravel(TreeNode* node)
{
     if(node == nullptr)
    {
        return;
    }
    MidTravel(node->left);
    std::cout<<*(int *)node->value<<" ";
    MidTravel(node->right);
}

void BinaryTree::PostTravel(TreeNode* node)
{
     if(node == nullptr)
    {
        return;
    }
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout<<*(int *)node->value<<" ";
}

BinaryTree::~BinaryTree()
{
    FreeNode(root);
}

void BinaryTree::FreeNode(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    FreeNode(node->left); //先放左孩子
    FreeNode(node->right);//再放右孩子
    delete node; //最后放自己
}

ElementType *BinaryTree::FindElement(const ElementType &element)
{
    return FindNode(root,element);
}

ElementType *BinaryTree::FindNode(TreeNode *node,const ElementType& element)
{
    if(node == nullptr)
    {
        return nullptr;
    }
    if(node->value == element)
    {
        return &node->value;
    }
    if(node->value < element)
    {
        return FindNode(node->right,element);
    }
    if(node->value > element)
    {
        return FindNode(node->left,element);
    }
    return nullptr;
}

BinaryTree::TreeNode *BinaryTree::GetMinNode(TreeNode *node)
{
    TreeNode * MinNode = node; //先让最小值等于它自己
    while(MinNode->left != nullptr) //当该节点的左边不为空，就一直往下找最小值
    {
        MinNode = MinNode->left;
    }
    return MinNode;
}

void BinaryTree::RemoveByElement(const ElementType &element)
{
    root = RemoveNode(root,element);
}

//返回值不属于它自己，所以加命名空间
BinaryTree::TreeNode* BinaryTree::RemoveNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
    {
        return nullptr;
    }

    if(node->value < element) //往右子树找
    {
        node->right = RemoveNode(node->right,element); //接到的返回值是下面return上来的空指针
    }

    else if(node->value > element) //往左子树找
    {
        node->left = RemoveNode(node->left,element);
    }

    else //找到了
    {
        //没有孩子，是叶子
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr; //返回给双亲
        }
        //左右孩子都存在
        else if(node->left != nullptr && node->right != nullptr)
        {
            TreeNode * min = GetMinNode(node->right); //拿到右子树中最小节点
            node->value = min->value; //把右子树中最小节点的值赋给当前要删除的节点
            node->right = RemoveNode(node->right,min->value); //删除右子树中最小的左节点的值
            //return node; //返回的还是原来的节点，只不过里面的值变了
        }
        //只有一个孩子，不论左右
        else
        {   //记住要拼上去的那个节点，是左孩子就取左不是就取右
            TreeNode *ChildNode = node->left ? node->left : node->right; 
            delete node; 
            node = ChildNode; //不管哪个孩子存在，删除这个节点后就把它的孩子接到被删除节点的位置
        }
    }

    if(LeftRightDev(node) > 1 ) //左失衡
    {
        if(LeftRightDev(node->left) > 0) //左左失衡，右旋，判断子树的子树
        {
            node = RotateRight(node);
        }
        else //左右失衡，左右旋
        {
            node = RotateLeftRight(node);
        }
    }

    if(LeftRightDev(node) < -1) //右边重
    {
        if(LeftRightDev (node->right) < 0) //右右失衡，左旋
        {
            node = RotateLeft(node);
        }
        else //右左失衡，右左旋
        {
            node = RotateRightLeft(node);
        }
    }
    return node;

    // if(node == nullptr)
    // {
    //     return nullptr;
    // }
    // if(node->value < element)
    // {
    //     node->right = RemoveNode(node->right,element);
    // }
    // else if(node->value > element)
    // {
    //     node->left = RemoveNode(node->left,element);
    // }
    // else
    // {
    //     if(node->left == nullptr && node->right == nullptr)
    //     {
    //         delete node;
    //         return nullptr;
    //     }
    //     else if(node->left != nullptr && node->right != nullptr)
    //     {
    //         TreeNode *min = GetMinNode(node->right);
    //         node->value = min->value;
    //         node->right = RemoveNode(node->right,min->value);
    //         return node;
    //     }
    //     else
    //     {
    //         TreeNode * childNode = node->left ? node->left : node->right;
    //         delete node;
    //         return childNode;
    //     }
    // return node;
    // }

}


BinaryTree::TreeNode *BinaryTree::RotateRight(TreeNode *node) //右旋
{
    TreeNode *t = node->left; // 提起操作，定义新的根节点
    node->left = t->right; //让原来的根节点的左孩子等于，t的右孩子
    t->right = node; // 新的根节点的右孩子空了出来，就把把原来的根节点node变成新根结点的右孩子
    return t;
}

//旋转会使根发生变化，所以要返回新的根TreeNode *
BinaryTree::TreeNode *BinaryTree::RotateLeft(TreeNode *node) //左旋
{
    TreeNode *t = node->right; 

    node->right = t->left;
    t->left = node;

    return t;

}

BinaryTree::TreeNode *BinaryTree::RotateLeftRight(TreeNode *node) //左右旋
{
    node->left = RotateLeft(node->left); //左子树左旋
    
    return RotateRight(node); //整棵树右旋之后返回
}

BinaryTree::TreeNode *BinaryTree::RotateRightLeft(TreeNode *node) //右左旋
{
    node->right = RotateRight(node->right); //右子树右旋
    
    return RotateLeft(node); //整棵树左旋
}

int BinaryTree::GetNodeHigh(TreeNode *node) //得到树的高度
{
    if(node == nullptr)
    {
        return 0;
    }
    int leftHigh = GetNodeHigh(node->left);
    int rightHigh = GetNodeHigh(node->right);
    int Maxhigh = (leftHigh > rightHigh ? leftHigh : rightHigh);
    return Maxhigh + 1;

}

int BinaryTree::LeftRightDev(TreeNode *node) //得到树的高度差
{
    if(node == nullptr)
    {
        return 0;
    }
    return GetNodeHigh(node->left) - GetNodeHigh(node->right);
}

//层序遍历
void BinaryTree::OrderTravel(TreeNode *node)
{
    if (node == nullptr)
        return;
    LinkQueue q1; //创建队列
    q1.Push(node);
    while (!q1.IsEmpty())
    {
        TreeNode *tarvePoint = (TreeNode*)q1.GetFront();
        std::cout <<*(int*)tarvePoint->value<< " ";
        q1.Pop();
        if (tarvePoint->left != nullptr)
        {
            q1.Push(tarvePoint->left);     
        }
        if (tarvePoint->right != nullptr)
        {
            q1.Push(tarvePoint->right);
        }
    }
}

void BinaryTree::NodeNum()
{
    int Onedu = 0;
    int Towdu = 0;
   NodeNum(root,Onedu,Towdu);
   std::cout<<"度为1的节点数为"<<Onedu<<std::endl;
   std::cout<<"度为2的节点数为"<<Towdu<<std::endl;
}

void BinaryTree::NodeNum(TreeNode * node,int &Onedu,int &Towdu)
{
   if(node == 0)
        return;

    int count1 = 0;
    int count2 = 0;
    if(node->left != nullptr && node->right == nullptr)
    {
        count1++;
    }
    if(node->left == nullptr && node->right != nullptr)
    {
        count1++;
    }
    if(node->right != nullptr && node->left != nullptr)
    {
        count2++;
    }

    Onedu += count1;
    Towdu += count2;

    NodeNum(node->left,Onedu,Towdu);
    NodeNum(node->right,Onedu,Towdu);
}